package shu.segment;

import java.util.Arrays;

public class SegmentTree<T> {
    private T[] source;
    private T[] data;
    private final Merger<T> merger;

    public SegmentTree(T[] arr, Merger<T> merger) {
        this.merger = merger;
        if (arr != null) {
            this.source = Arrays.copyOf(arr, arr.length);
            int height = (int) Math.ceil(Math.log(this.source.length) / Math.log(2) + 1);
            int datalength = (int) Math.pow(2, height) - 1;
            this.data = (T[]) new Object[datalength];
            buildingSegmentTree(0, this.source.length - 1, 0);
        }

    }

    public static void main(String[] args) {
        Integer[] arr = {19, 2, 18, 22, 5};
        SegmentTree<Integer> segmentTree = new SegmentTree<>(arr, (Integer a, Integer b) -> a + b);
        System.out.println(segmentTree);

        Integer result = segmentTree.getRangValue(2, 3);

        System.out.println("arr[1:3]=" + result);

        segmentTree.update(2, 10);
        result = segmentTree.getRangValue(1, 3);
        System.out.println("arr[1:3]=" + result);
        System.out.println(segmentTree);
    }

    /**
     * 构建线段树
     *
     * @param start 区间的开始
     * @param end   区间的结尾
     * @param index 线段树对应[start:end]区间的索引
     */
    private void buildingSegmentTree(int start, int end, int index) {
//递归到底的情况
        if (start == end) {
            this.data[index] = this.source[start];
            return;
        }

        // 2、递归操作
        //左孩子，右孩子，中间节点
        int leftindex = 2 * index + 1;
        int rightindex = leftindex + 1;
        int mid = start + (end - start) / 2;
        //递归方法
        buildingSegmentTree(start, mid, leftindex);
        buildingSegmentTree(mid + 1, end, rightindex);
        //融合
        this.data[index] = this.merger.merge(this.data[leftindex], this.data[rightindex]);
    }

    public T getRangValue(int from, int to) {
        if (from < 0 || to >= this.source.length || from > to) {
            throw new IllegalArgumentException("error");
        }
        return query(0, this.source.length - 1, 0, from, to);
    }

    /**
     * 进行查询操作
     *
     * @param start 线段树结点所表示区间的start
     * @param end   线段树结点所表示区间的end
     * @param index 线段树上结点的索引
     * @param from  查询区间的开始
     * @param to    查询区间的结尾
     * @return
     */
    public T query(int start, int end, int index, int from, int to) {
        //递归到底的情况
        if (start == from && end == to) {
            return this.data[index];
        }
        int leftindex = 2 * index + 1;
        int rightindex = leftindex + 1;
        int mid = start + (end - start) / 2;
        if (from > mid) {
            return query(mid + 1, end, rightindex, from, to);
        } else if (to <= mid) {
            return query(start, mid, leftindex, from, to);
        } else {
            T rightvalue = query(mid + 1, end, rightindex, mid + 1, to);
            T leftvalue = query(start, mid, leftindex, from, mid);
            return this.merger.merge(rightvalue, leftvalue);
        }

    }

    /**
     * 更新源数组索引为index位置的值为val
     *
     * @param site 索引
     * @param val  值
     */
    public void update(int site, T val) {
        if (site < 0 || site >= this.source.length) {
            throw new IllegalArgumentException("index is invalid!");
        }
        // 重新渲染线段树
        update(0, this.source.length - 1, 0, site, val);
    }

    private void update(int start, int end, int index, int site, T val) {
        if (start == end && start == site) {
            this.data[index] = this.source[site] = val;
            return;
        }
        int leftindex = 2 * index + 1;
        int rightindex = leftindex + 1;
        int mid = start + (end - start) / 2;
        if (mid < site) {
            update(mid + 1, end, rightindex, site, val);
        } else {
            update(start, mid, leftindex, site, val);
        }
        this.data[index] = this.merger.merge(this.data[leftindex], this.data[rightindex]);


    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        if (this.data != null && this.data.length != 0) {
            Arrays.stream(this.data).forEach(item -> {
                sb.append(item + ",");
            });
        }
        return sb.deleteCharAt(sb.length() - 1).append("]").toString();
    }
}
